package com.rui.study.algorithm.P_八皇后;

import java.util.Arrays;

/**
 * @program: study_20180903
 * @description: N皇后_提交_2
 * @author: Yaowr
 * @create: 2018-09-04 15:17
 **/
public class N皇后_提交_2 {
    private String QUEEN = "O";
    private String EMPTY = " ";
    private String NAN = "X";

    private int result = 0;

    public int totalNQueens(int n) {
        /* 初始化棋盘 */
        String[][] board = new String[n][n];
        for (int i = 0; i < n; i++) {
            Arrays.fill(board[i], EMPTY);
        }
        locate(board, 0);
        return result;
    }

    /**
     * 递归落子
     * @param board
     * @return
     */
    public boolean locate(String[][] board, int row) {
        if (board == null || row > board.length - 1)
            return false;
        int n = board.length;

        /* 遍历当前行的落子位置 */
        for (int col = 0; col < n; col++) {
            if (!board[row][col].equals(EMPTY))     // 寻找空位置
                continue;

            // 摆放'当前行'的皇后
            board[row][col] = QUEEN;
            // 复盘
            markDisable(board, row, col);
            if (row == n - 1) {     // 最后一个皇后
                result += 1;
            }

            // 摆放'下一行'的皇后
            if (!locate(board, row + 1)) {
                // 若'下一行'的皇后 无处安放！！！则移动'当前行'的皇后
                board[row][col] = EMPTY;
                // 清盘
                markEnable(board);
                // 复盘
                markDisable(board);
            }
        }
        return false;
    }

    private void markDisable(String[][] board, int xLocation, int yLocation) {
        mark(board, xLocation, yLocation, NAN);
    }

    private void markDisable(String[][] board) {
        if (board == null)
            return;
        int n = board.length;

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                if (board[x][y].equals(QUEEN)) {
                    markDisable(board, x, y);
                }
            }
        }
    }

    private void markEnable(String[][] board) {
        if (board == null)
            return;
        int n = board.length;

        for (int x = 0; x < n; x++) {
            for (int y = 0; y < n; y++) {
                if (board[x][y].equals(NAN)) {
                    board[x][y] = EMPTY;
                }
            }
        }
    }

    /**
     * 指定'皇后'位置，标记或取消不可用位置
     * @param board
     * @return
     */
    private void mark(String[][] board, int xLocation, int yLocation, String flag) {
        if (board == null)
            return;
        int n = board.length;

        // 行
        for (int y = 0; y < n; y++) {
            if (y != yLocation) {
                board[xLocation][y] = flag;
            }
        }

        // 列
        for (int x = 0; x < n; x++) {
            if (x != xLocation) {
                board[x][yLocation] = flag;
            }
        }

        // 对角
        int startX = 0, startY = 0;
        if (xLocation > yLocation) {
            startX = xLocation - yLocation;
        } else if (xLocation < yLocation) {
            startY = yLocation - xLocation;
        }
        int beginX = xLocation + yLocation < n ? xLocation + yLocation : n - 1;
        int beginY = xLocation + yLocation < n ? 0 : xLocation + yLocation - (n - 1);
        for (int y = 0; y < n; y++) {
            // 左
            if (y >= beginY && beginX >= 0) {
                if (y != yLocation) {
                    board[beginX][y] = flag;
                }
                beginX--;
            }
            // 右
            if (y >= startY && startX < n) {
                if (y != yLocation) {
                    board[startX][y] = flag;
                }
                startX++;
            }
        }
    }

}
